package 动态规划;

import java.util.Arrays;

public class No64最小路径和 {

    /**
     * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
     * 说明：每次只能向下或者向右移动一步。
     *
     * 示例 1：
     * 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
     * 输出：7
     * 解释：因为路径 1→3→1→1→1 的总和最小。
     * 示例 2：
     * 输入：grid = [[1,2,3],[4,5,6]]
     * 输出：12
     */

    public int minPathSum(int[][] grid) {

        int allLength=grid.length;
        int itemLength=grid[0].length;
        int[][] db=new int[allLength][itemLength];

        /**
         * 不想越界判断?那就从 角点(x-1,y-1)开始判断
         * 最边边补上时,需要注意加上累计数值
         */
        //把角点也加进去,结果就不用加了
        db[allLength-1][itemLength-1]=grid[allLength-1][itemLength-1];
        for (int i = allLength-2; i >=0; i--) {
            //写最后的竖排
            db[i][itemLength-1]=grid[i][itemLength-1]+db[i+1][itemLength-1];
        }
        for (int i = itemLength-2; i >=0; i--) {
            //写最底排
            db[allLength-1][i]=grid[allLength-1][i]+db[allLength-1][i+1];
        }

        for (int i = allLength-2; i >=0 ; i--) {
            for (int j = itemLength-2; j>=0; j--) {
                db[i][j]=grid[i][j]+Math.min(db[i][j+1],db[i+1][j]);
            }
        }

        return db[0][0];
    }

    public static void main(String[] args) {
        No64最小路径和 n=new No64最小路径和();
        int[][] arr={
                    {1,2,3},
                    {4,5,6}
                    };
        int result = n.minPathSum(arr);
        System.out.println(result);
    }

}
